The need for a circumscriptive formalism that allows for simple yet elegantmodular problem representation has led Lifschitz (AIJ, 1995) to introducenested abnormality theories (NATs) as a tool for modular knowledgerepresentation, tailored for applying circumscription to minimize exceptionalcircumstances. Abstracting from this particular objective, we propose L_{CIRC},which is an extension of generic propositional circumscription by allowingpropositional combinations and nesting of circumscriptive theories. As shown,NATs are naturally embedded into this language, and are in fact of equalexpressive capability. We then analyze the complexity of L_{CIRC} and NATs, andin particular the effect of nesting. The latter is found to be a source ofcomplexity, which climbs the Polynomial Hierarchy as the nesting depthincreases and reaches PSPACE-completeness in the general case. We also identifymeaningful syntactic fragments of NATs which have lower complexity. Inparticular, we show that the generalization of Horn circumscription in the NATframework remains CONP-complete, and that Horn NATs without fixed letters canbe efficiently transformed into an equivalent Horn CNF, which impliespolynomial solvability of principal reasoning tasks. Finally, we also studyextensions of NATs and briefly address the complexity in the first-order case.Our results give insight into the ``cost'' of using L_{CIRC} (resp. NATs) as ahost language for expressing other formalisms such as action theories,narratives, or spatial theories.
展开▼
